home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / simula / books / books.lha / kirkerud / quicksorttest.sim < prev    next >
Text File  |  1993-08-16  |  2KB  |  71 lines
  1. begin
  2.  
  3.   procedure Quicksort(table, low_bound, high_bound);
  4.       integer array table;  integer low_bound, high_bound;
  5.     !  Sorts the elements in table(low_bound : high_bound) in non-decreasing order;
  6.   if low_bound < high_bound then
  7.   begin integer some_value, last_below, last_equal,  first_above, ind, x;
  8.     some_value  := table(low_bound);
  9.     last_below  := low_bound - 1;
  10.     last_equal  := low_bound;
  11.     first_above := high_bound + 1;
  12.     ind         := low_bound + 1;
  13.     while ind < first_above do
  14.       begin
  15.         x := table(ind);      
  16.         if x < some_value then
  17.           begin
  18.             last_below := last_below + 1;     last_equal := last_equal + 1;
  19.             table(ind) := table(last_below);  table(last_below) := x;
  20.             ind := ind + 1;
  21.           end else
  22.         if x = some_value then
  23.           begin last_equal := last_equal + 1;  ind := ind + 1 end
  24.         else begin
  25.             first_above := first_above - 1;
  26.             table(ind) := table(first_above);  table(first_above) := x;
  27.           end;
  28.       end;
  29.     Quicksort(table,   low_bound, last_below);
  30.     Quicksort(table, first_above, high_bound);
  31.   end of Quicksort;
  32.   
  33.   procedure qt(a, low, hi); integer array a; integer low, hi;
  34.     begin integer ind, error_count; Boolean sort_error;
  35.       outtext("Before sorting: "); outimage;
  36.       for ind := low step 1 until hi do outint(a(ind), 5); 
  37.       outimage;
  38.       Quicksort(a, low, hi);
  39.       outtext("After sorting: "); outimage;
  40.       for ind := low step 1 until hi do outint(a(ind), 5); 
  41.       outimage;
  42.       for ind := low + 1 step 1 until hi do
  43.         if a(ind-1) > a(ind) then
  44.           begin 
  45.             if not sort_error then 
  46.               begin outtext("First sort-error at index "); outint(ind-1, 0) end;
  47.             sort_error := true;
  48.             error_count := error_count + 1;
  49.           end;
  50.       if not sort_error 
  51.         then outtext("Sorted correctly!")
  52.         else begin outint(error_count, 0); outtext(" sort-errors!") end;
  53.       outimage; outimage;
  54.     end; 
  55.  
  56.   integer array a(1 : 50);
  57.  
  58.   integer ind, seed;
  59.  
  60.   for ind := 1 step 1 until 50 do a(ind) := ind; 
  61.   qt(a, 1, 50);
  62.   
  63.   for ind := 1 step 1 until 50 do a(ind) := -ind; 
  64.   qt(a, 1, 50);
  65.   
  66.   seed := 123579;
  67.   for ind := 1 step 1 until 50 do a(ind) := randint(1, 50, seed); 
  68.   qt(a, 1, 50);
  69.   
  70. end
  71.